Подбор плотностей тел

Данная процедура решает обратную задачу - подбор плотностей блоков в сеточной 3D модели, заданной через 3D ТОС, по соответствующему ей гравитационному полю, заданному сеточной 2D моделью через 2D ТОС.

Исходные данные

1. 3D ТОС, содержащая классификационное свойство, задающее разбиение пространства на блоки.
2. 2D ТОС, содержащее свойство, задающее гравитационное поле.
3. (опционально) два свойства в 3D ТОС, задающие ожидаемую плотность блока и разброс.

Формализм

Каждому классу (блоку) с индексом ${\displaystyle i}$ разбиения на ${\displaystyle n}$ классов (блоков) соответствует модель поля ${\displaystyle \overline{u_i}}$, которое порождал бы блок, состоящий из ячеек класса ${\displaystyle i}$ с эффективной плотностью ${\displaystyle 1g/{cm}^3}$. Множество всех возможных ${\displaystyle \{\overline{a}\}}$ составляет линейное пространство с векторами ${\displaystyle \overline{a}}$.

Измеренное гравитационное поле обозначим ${\displaystyle \overline{b}}$. Тогда плотности блоков ${\displaystyle \overline{x}=\{{x^{\text{'}}}_i\}}$ определяются решением линейной задачи:

${\displaystyle A^{\text{'}}\overline{x}=\overline{b},}$ (1)

где матрица ${\displaystyle A^{\text{'}}}$ состоит из вектор-столбцов ${\displaystyle \overline{a_i}}$. Так как система (1) наверняка несовместна, вместо ней решается задача минимизации функционала:

${\displaystyle F^{\text{'}}\left(x\right)=\Vert A^{\text{'}}\overline{x}-\overline{b}\Vert 0}$,

Где ${\displaystyle \Vert \bullet \Vert }$ – евклидова норма (длина вектора).

Считаем, что поле известно с точностью до константы. Добавляется единичный вектор и задача сводится к отысканию минимума следующего функционала:

${\displaystyle F\left(x\right)=\Vert A^{\text{'}}\overline{x}+\xi \overline{u}-\overline{b}\Vert \to mi{n}_{\overline{x},\xi }}$, (2)

${\displaystyle \overline{u}=(1,1,\dots ,1)}$.

Чтобы исключить единичный вектор, каждый вектор-столбец ${\displaystyle \overline{a_i}}$ и ${\displaystyle \overline{b}}$ приводят к виду, ортогональному ${\displaystyle \overline{u}}$:

${\displaystyle a_i=\overline{a_i}-\overline{u}\left(\overline{a_i}\frac{\overline{u}}{\Vert \overline{u}\Vert }\right),}$

${\displaystyle b=\overline{b}-\overline{u}\left(\overline{b}\frac{\overline{u}}{\Vert \overline{u}\Vert }\right).}$

Тогда задача выглядит следующим образом:

${\displaystyle F\left(x\right)=\Vert Ax-b\Vert \to mi{n}_{\overline{x}}}$</math>.

В случае, если задача некорректна, можно использовать регуляризацию Тихонова в её простейшем случае:

${\displaystyle \hat{F}\left(x\right)=(1-\alpha )\Vert Ax-b\Vert +\alpha \Vert x\Vert .}$ (3)

Регуляризация уменьшает некорректность, перемещая решение ближе к нулевому вектору за счёт ухудшения точности приближения вектора ${\displaystyle b}$. Параметр ${\displaystyle \alpha }$ определяет, насколько сильно влияет регуляризация на решение, и меняется в диапазоне от 0 (тогда ${\displaystyle \hat{F}\left(x\right)=F\left(x\right)}$) до 1 (тогда ${\displaystyle \hat{F}\left(x\right)=\Vert x\Vert }$ и его минимум достигается при ${\displaystyle x=(0,0,\dots ,0)}$).

Функционал (3) достигает минимума на:

${\displaystyle x={(A^{T}A+\alpha I)}^{-1}{A}^{T}b}$

Задача с ограничениями

Для решения задачи с ограничениями используется алгоритм BVLS[1].

Особенности

Если в исходных данных отсутствуют пропуски, то для двух наборов значений плотностей, отличающихся на константу (${\displaystyle \overline{x}}$ и ${\displaystyle {\overline{x}}^{\prime }=\overline{x}+C}$), их поля равны (${\displaystyle A\overline{x}=A{\overline{x}}^{\prime }}$). То есть, плотности заданы с точностью до некоторой константы. Также при некоторых условиях такая особенность может иметь место и для некоторого подмножества ${\displaystyle K=i\subset (1...N)}$ тел (классов). При использовании регуляризации значение ${\displaystyle C}$ подбирается так, чтобы плотности были близки к нулю, иначе либо ${\displaystyle C}$ определяется исходя из заданных ограничений, либо выбирается случайно, в том числе может принять и неадекватно большую (положительную или отрицательную) величину. В этом случае надо относиться к плотностям как к эффективным, и далее подобрать и прибавить некоторую константу.

Алгоритм

Процедура состоит в выполнении следующих шагов:

1. Анализ классификационного свойства, во время которого выясняется количество классов и их идентификаторы.
2. Вычисление полей блоков – вектор-столбцов ${\displaystyle a_i}$ матрицы ${\displaystyle A}$.
3. Вычисление матрицы ${\displaystyle A^{T}A}$ и вектора ${\displaystyle A^T\overline{b}}$.
4. Вычисление ${\displaystyle x}$. Если матрица не имеет обратной, выдаётся соответствующее сообщение; в этом случае рекомендуется увеличить параметр ${\displaystyle \alpha }$.
   1. В случае отсутствия ограничений - через разложение матрицы ${\displaystyle (A^{T}A+\alpha I)}$.
   2. В случае заданных ограничений - через алгоритм BVLS[1].
5. Запись результата в целевую 3D ТОС в виде распределения плотностей.

Параметры

• Исходная ТОС 2D и исходное свойство: ТОС и имя свойства, содержащие исходное поле.
• Экстраполяция - использовать ли зеркальную экстраполяцию. Если по каким-то причинам требуется использовать стандартную экстраполяцию, то её необходимо сделать отдельно.
• Высота поля (Z) - высота, на которой находится плоскость, содержащая сетку, в которой задано поле, м.
• Регуляризация - выполнять ли регуляризацию.
• Альфа - коэффициент регуляризации ${\displaystyle \alpha }$.
• Альфа, дБ - коэффициент регуляризации ${\displaystyle \alpha }$ в логарифмических единицах.
• ТОС 3D - ТОС 3D, содержащая классификацию и ограничения, если нужны.
• Имя классового свойства - имя свойства в ТОС 3D, определяющего разбиение на блоки.
• Использовать ограничения - использовать ли ограничения на вычислемые плотности блоков. При заданных ограничениях все плотности должны быть внутри интервала.
• Середина интервала - свойство в 3D ТОС, задающее для каждого блока центр интервала, в котором ищется решение.
• Полуширина интервала - свойство в 3D ТОС, задающее для каждого блока полуширину интервала, в котором ищется решение.
• Целевое свойство - имя свойства в ТОС 3D, в которое записывается результат - распределение плотностей.

Рекомендации по использованию

Перед запуском алгоритма необходимо убедиться, что разбиение 3-хмерной ТОС «разумно».

Сложность представляет подбор параметра силы регуляризации ${\displaystyle \alpha }$, так как в нём мало предметного смысла. Следует начинать с ${\displaystyle \alpha =0}$. При этом следует сохранять поля классов, так как эта процедура – самая времязатратная. Если не удаётся рассчитать обратную матрицу или значения плотностей варьируются в областях, далёких от допустимых или разумных, следует увеличивать параметр ${\displaystyle \alpha }$.

Регуляризация и ограничения

На данный момент нет возможности задать одновременно и ограничения, и коэффициент регуляризации.

Список литературы

1. P.B. Stark, R.L. Parker "Bounded-Variable Least-Squares: an Algorithm and Applications", Computational Statistics. 10:129-141